﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Problems.Traversals;
using Algoritmia.Utils;

namespace Algoritmia.Problems.ConnectedComponents
{
    public class GraphTraversalConnectedComponentsFinder<T> : IConnectedComponentsFinder<T>
    {
        private readonly Func<IDigraph<T>, IGraphTraverser<T, Tuple<T,T>>> _createTraverser;

        public GraphTraversalConnectedComponentsFinder(Func<IDigraph<T>,IGraphTraverser<T,Tuple<T,T>>> createTraverser = null)
        {
            _createTraverser = createTraverser ?? (g => new BreadthFirstTraverser<T, Tuple<T,T>>());
        }

        #region IConnectedComponentsFinder<T> Members

        public IEnumerable<IEnumerable<T>> ConnectedComponents(IDigraph<T> g)
        {
            var traverser = _createTraverser(g);
            var component = new List<T>();
            var equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison<T>();
            bool first = true;
            foreach(var tuple in traverser.FullTraverse(g,(u,v) => new Tuple<T, T>(u,v)))
            {
                if ( equalityComparison(tuple.Item1,tuple.Item2) && !first)
                {
                    yield return component;
                    component = new List<T>();
                }
                component.Add(tuple.Item2);
                first = false;
            }
            yield return component;
        }

        #endregion
    }
}
